package audiophobia;

import java.io.PrintStream;
import java.util.Scanner;

/**
 * audiophobia UVA problem
 * @author Jonas Jeske www.inf.ufrgs.br/~jjeske
 * status: Accepted !
 *
 */
public class Main {
	
	public static void main(String[] args){
		Main audiophobia = new Main();
		audiophobia.begin();
	}
	
	private int C,S,Q;
	private int[][] graph;
	Scanner entrada = new Scanner(System.in);
	PrintStream saida = new PrintStream(System.out);
	private static int INFINITO = 99999999;
	
	/* input
	 * 
7 9 3
1 2 50
1 3 60
2 4 120
2 5 90
3 6 50
4 6 80
4 7 70
5 7 40
6 7 140
1 7
2 6
6 2
7 6 3
1 2 50
1 3 60
2 4 120
3 6 50
4 6 80
5 7 40
7 5
1 7
2 4
0 0 0
	 */
	public void begin(){
		
		int caso = 0;
		
		while (entrada.hasNext()) {
			caso++;	
			C = entrada.nextInt(); //corners
			S = entrada.nextInt(); //Streets
			Q = entrada.nextInt(); //Queries
			if( (C == 0) && (S==0) && (Q==0)){
				break;
			}
			if(caso > 1){
				saida.printf("\n");
			}
			
			graph = new int[C][C];
			
			for (int i = 0; i < C; i++) {
				for (int j = 0; j < C; j++) {
					graph[i][j] = INFINITO;
				}
			}
			int c1,c2,value;
			
			for (int i = 0; i < S; i++) {
					c1 = entrada.nextInt();
					c2 = entrada.nextInt();
					value = entrada.nextInt();;
					graph[c1-1][c2-1] = value;
					graph[c2-1][c1-1] = value;			
			}
			
			//search queries
			FloydWarshall();
			saida.printf("Case #%d\n",caso);
			int q1,q2;
			for (int i = 0; i < Q; i++){
					q1 = entrada.nextInt();
					q2 = entrada.nextInt();
					if(graph[q1-1][q2-1] < INFINITO){
						saida.printf("%d\n",graph[q1-1][q2-1]);
					} else {
						saida.printf("no path\n");
					}							
			}			
		}
	}
	
	/* output
	 *
Case #1
80
60
60
 
Case #2
40
no path
80

	 */


	public void FloydWarshall(){
		  // algoritmo de minmax de floyd Warshall
		  for(int k=0;k<C;k++){
		    for(int i=0;i<C;i++){
		      for(int j=0;j<C;j++){
		        graph[i][j] = Math.min( graph[i][j], Math.max( graph[i][k],graph[k][j]) );
		      }
		    }
		  }
		}
}
